/***************************************************************************************
* Copyright (c) 2014-2022 Zihao Yu, Nanjing University
*
* NEMU is licensed under Mulan PSL v2.
* You can use this software according to the terms and conditions of the Mulan PSL v2.
* You may obtain a copy of Mulan PSL v2 at:
*          http://license.coscl.org.cn/MulanPSL2
*
* THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
* EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
* MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
*
* See the Mulan PSL v2 for more details.
***************************************************************************************/

#include <isa.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <memory/paddr.h>
/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <regex.h>

word_t isa_reg_str2val(const char *s, bool *success);

enum {
  TK_NOTYPE = 256, TK_REG, TK_HEX,TK_DEC,TK_EQ,
  TK_NOTEQ,TK_LQ,TK_GQ,TK_AND,TK_OR,TK_END

  /* TODO: Add more token types */

};
enum {
  NUMBER=TK_END+1
};
static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */
  {" +", TK_NOTYPE},    // spaces
  {"\\+", '+'},         // plus or pos('+' has the special meaning in regex,it should use '/+' to describe '+')
  {"\\-", '-'},         // minus or neg
  {"\\*", '*'},         // mul or ref
  {"/", '/'},           // div
  {"\\(",'('},
  {"\\)",')'},    
  {"(\\$){2}0",TK_REG}, // reg $0
  {"\\$[a-zA-Z]{1,2}[0-9]*",TK_REG}, //$reg
  {"0[xX][0-9a-fA-F]+",TK_HEX}, //hexadecimal number
  {"[0-9]+",TK_DEC},//decimal number
  {"<=",TK_LQ},
  {">=",TK_GQ},
  {"!=",TK_NOTEQ},
  {"<",'<'},
  {">",'>'},
  {"==", TK_EQ},  // equal
  {"&&", TK_AND},
  {"\\|\\|", TK_OR},

};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}


typedef struct token {
  int type;
  char str[64];       //type=NUMBER *(*uint32_t)str
} Token;

static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;
  nr_token = 0;
  char* endptr;
  bool success;
  char str_buffer[64]={};
  while (e[position] != '\0') {
    /* Try all rules one by one. */
    
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        // Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",i, rules[i].regex, position, substr_len, substr_len, substr_start);

        strncpy(str_buffer,substr_start,substr_len);
        str_buffer[substr_len]='\0';
        position += substr_len;
        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */
        
        switch (rules[i].token_type) {
          case '+':
          case '-':
          case '*':
          case '/':
          case '(':
          case ')':
          case '<':
          case '>':
          case TK_LQ:
          case TK_GQ:
          case TK_EQ:
          case TK_NOTEQ:
          case TK_AND:
          case TK_OR:
            tokens[nr_token++].type=rules[i].token_type;
            break;
          case TK_REG:
            tokens[nr_token].type=NUMBER;
            *(uint32_t*)tokens[nr_token].str=isa_reg_str2val(str_buffer+1,&success);
            if(!success)return false;
            nr_token++;
            break;
          case TK_HEX:
            tokens[nr_token].type=NUMBER;
            *(uint32_t*)tokens[nr_token].str=strtoul(str_buffer,&endptr,16);
            if(*endptr!='\0')return false;
            nr_token++;
            break;
          case TK_DEC:
            tokens[nr_token].type=NUMBER;
            *(uint32_t*)tokens[nr_token].str=strtoul(str_buffer,&endptr,10);
            if(*endptr!='\0')return false;
            nr_token++;
            break;
          case TK_NOTYPE: 
            break;
        }
        break;
      }
    }

    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}



static bool check_parentheses(int left,int right){
  int left_bracket_count =1;
  if(tokens[left].type=='(' && tokens[right].type==')'){
    for(left++;left<right;left++){
      if(left_bracket_count==0)return false;
      if(tokens[left].type=='('){
        left_bracket_count++;
      }
      else if(tokens[left].type==')'){
        left_bracket_count--;
      }
    }
    if(left_bracket_count==1)return true;  
  }
  return false;
}
static bool check_expr_parentheses(int left,int right){
  int left_bracket_count =0;
    for(;left<=right;left++){
      if(left_bracket_count<0)return false;
      if(tokens[left].type=='('){
        left_bracket_count++;
      }
      else if(tokens[left].type==')'){
        left_bracket_count--;
      }
    }
  if(left_bracket_count!=0)return false;
  return true;
}
static struct {
  int x;
  int level;
} op_prioritys[]={
  {TK_AND,0},{TK_OR,1},{TK_EQ,2},{TK_NOTEQ,2},{'<',3},{'>',3},{TK_LQ,3},
  {TK_GQ,3},{'+',4},{'-',4},{'*',5},{'/',5},
};

static inline int find_priority(int op){
  for(int i=0;i<ARRLEN(op_prioritys);i++){
    if(op==op_prioritys[i].x){
      return op_prioritys[i].level;
    }
  }
  return -1;
}

static inline bool check_self_op(int n){
    switch (n)
    {
    case '+':
    case '-':
    case '*':
      return true;
    default:
      return false;
    }
}
static int skip_num_or_subexpr(int left,int right){
  while(check_self_op(tokens[left].type)){
    left++;
  }
  if(tokens[left].type==NUMBER){
    return left+1;
  }
  int left_bracket_count=0;
  for(;left<=right;left++){
    if(tokens[left].type=='(')left_bracket_count++;
    else if(tokens[left].type==')')left_bracket_count--;
    if(left_bracket_count==0)break;
    }
  return left+1;
}

static int find_main_opeator(int left,int right){
    #define EXPECT_NUM_OR_SUBEXPR 1
    #define EXPECT_OP 0
    int expect=EXPECT_NUM_OR_SUBEXPR;
    int main_op_pos=-1;
    int piority=0x7FFFFFFF;
    while(left<=right){
      if(expect==EXPECT_NUM_OR_SUBEXPR){
        left=skip_num_or_subexpr(left,right);
        expect=EXPECT_OP;
      }
      else{
        int np=find_priority(tokens[left].type);
        if(np<piority){
          piority=np,main_op_pos=left;
          if(piority==0) return main_op_pos;
        }
        left++;
        expect=EXPECT_NUM_OR_SUBEXPR;
      }
    }
    return main_op_pos;
}

static uint32_t eval(int left,int right,bool *success){  //calculate the expression by recursion
  if(!(left<=right && *success)){
    *success=false;
    return 0;
  }
  else if(left == right){
    if(tokens[left].type==NUMBER){
      return *(uint32_t*)tokens[left].str;
    }
    else{
      *success=false;
      return 0;
    }
  }
  else if(check_parentheses(left,right)){
    return eval(left+1,right-1,success);
  }
  else{
    int p=find_main_opeator(left,right);
    if(p!=-1){
      uint32_t val1=eval(left,p-1,success);
      uint32_t val2=eval(p+1,right,success);
      switch(tokens[p].type){
        case '+': return val1 + val2;
        case '-': return val1 - val2;
        case '*': return val1 * val2;
        case '/': return val1 / val2;
        case '<': return val1 < val2;
        case '>': return val1 > val2;
        case TK_LQ: return val1 <= val2;
        case TK_GQ: return val1 >= val2;
        case TK_EQ: return val1 == val2;
        case TK_NOTEQ: return val1 != val2;
        case TK_AND: return val1 && val2;
        case TK_OR: return val1 || val2;
        default: assert(0);
      }
    }
    else{
      uint32_t val1=eval(left+1,right,success);
      switch(tokens[left].type){
        case '+': return val1;
        case '-': return -val1;
        case '*': return paddr_read(val1,4);
        //case '*': return ;
        default: assert(0);
      }
    }
  }
  return 0;
}

uint32_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }
  if(!check_expr_parentheses(0,nr_token-1)){
    *success = false;
    return 0;
  }
  /* TODO: Insert codes to evaluate the expression. */
  *success=true;
  
  return eval(0,nr_token-1,success);
}
